// Problem: 
// Contest: 
// URL: 
// Memory Limit: 
// Time Limit: 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
vector<vector<int>> a(65,vector<int>(3));
auto b=a;
vector<int> dp(32005);
int c1(int i,int x)
{
	return a[i][x];
}
int c2(int i,int x,int y)
{
	return a[i][x]+a[i][y];
}
int c3(int i,int x,int y,int z)
{
	return a[i][x]+a[i][y]+a[i][z];
}
int R(int i,int x)
{
	return a[i][x]*b[i][x];
}
signed main()
{
	int T=1;
//	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=m;i++)
		{
			int v,p,q;
			cin>>v>>p>>q;
			if(!q)
			{
				a[i][0]=v;
				b[i][0]=p;
			}
			else
			{
				if(a[q][1]==0)
				{
					a[q][1]=v;
					b[q][1]=p;
				}
				else
				{
					a[q][2]=v;
					b[q][2]=p;
				}
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(!c1(i,0))continue;
			for(int j=n;j>=0;j--)
			{
				if(j>=c1(i,0))dp[j]=max(dp[j],dp[j-c1(i,0)]+R(i,0));
				if(j>=c2(i,0,1))dp[j]=max(dp[j],dp[j-c2(i,0,1)]+R(i,0)+R(i,1));
				if(j>=c2(i,0,2))dp[j]=max(dp[j],dp[j-c2(i,0,2)]+R(i,0)+R(i,2));
				if(j>=c3(i,0,1,2))dp[j]=max(dp[j],dp[j-c3(i,0,1,2)]+R(i,0)+R(i,1)+R(i,2));
			}
		}
		cout<<dp[n];
	}
	return 0;
}
